﻿// 197. 阶乘分解.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//


/*
https://www.acwing.com/problem/content/199/

给定整数 N，试把阶乘 N! 分解质因数，按照算术基本定理的形式输出分解结果中的 pi 和 ci 即可。

输入格式
一个整数 N。

输出格式
N! 分解质因数后的结果，共若干行，每行一对 pi,ci，表示含有 pcii 项。按照 pi 从小到大的顺序输出。

数据范围
3≤N≤106
输入样例：
5
输出样例：
2 3
3 1
5 1
样例解释
5!=120=23∗3∗5
*/

#include <iostream>
#include <vector>

using namespace std;

const int N = 1000010;
int primes[N], cnt;
bool st[N];
int n;


void init() {
    for (int i = 2; i <= n; i++) {
        if (!st[i]) primes[cnt++] = i;
        for (int j = 0; primes[j] <= n / i; j++)
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}


int main()
{
    cin >> n;
    init();
    vector<int>ans;
    for (int i = 0; i < cnt; i++) {
        int p = primes[i];
        int cpn = n; int cnt = 0;
        while (cpn) {
            cnt += cpn / p;
            cpn /= p;
        }
        if (cnt) {
            ans.push_back(p);
            ans.push_back(cnt);
        }
    }

    for (int i = 0; i < ans.size(); i += 2) {
        cout << ans[i] << " " << ans[i + 1] << endl;
    }

    return 0;
}

